public class Solution647 {
    public int countSubstrings(String s) {
        int ans=0;
        boolean[][] f=new boolean[s.length()][s.length()];
        for (int i=s.length()-1;i>=0;i--){
            f[i][i]=true;
            ans++;
            for (int j=i+1;j<s.length();j++){
                f[i][j]=s.charAt(i)==s.charAt(j);
                if (j-1>i+1){
                    f[i][j]&=f[i+1][j-1];
                }
                if (f[i][j]){
                    ans++;
                }
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(new Solution647().countSubstrings("aaa"));
    }
}
